package Z.dailyExercise.April;

import java.util.ArrayList;
import java.util.List;

public class _114二叉树展开为链表 {

    public void flatten(TreeNode root) {

        List<TreeNode> list = new ArrayList<>();
        pre(root,list);
        int size = list.size();
        for (int i =1;i<size;i++){
            //TreeNode cur = node;
            TreeNode cur = list.get(i);
            TreeNode prev = list.get(i-1);
            prev.right = cur;
            prev.left = null;
        }


    }
    public void pre(TreeNode node, List<TreeNode> list){
        if (node!=null){
            list.add(node);

            pre(node.left,list);
            pre(node.right,list);


        }
    }


    /**
     * 参考先驱节点
     * 从上往下一次处理
     */
    public void flatten1(TreeNode root) {
        TreeNode cur = root;
        while (cur != null){
            TreeNode next = cur.left;
            if (next!= null){
                TreeNode predecessor = next;
                while (predecessor.right!= null){
                    predecessor = predecessor.right;
                }
                predecessor.right = cur.right;
                cur.right = next;
                cur.left = null;
            }
            cur = cur.right;

        }


    }



    }
